Fault Tolerance for Outputs and Clients

We have already discussed how to make a group of state machines tolerant to faults. However, the output of the state machines goes to the output devices read by the voter devices. The output and voter devices can also fail. In this lesson, we will discuss how to deal with such failures.

Fault-tolerant outputs#

If we use a single output device for an ensemble of replicas, the resulting system would not be $t$ fault-tolerant. This is because the failure of this node can result in the system being unable to generate correct outputs. Let's see how we can provide fault tolerance in this scenario:

Outputting externally#

A major proportion of applications of state machine replication requires outputting to a client, system, or node not part of the group of replicas. Suppose a system of replicated state machines has an output node that collects outputs from all replicas and sends the combined output to its destination. In that case, failure of the output node will result in the system generating incorrect outputs. Therefore, we must develop a solution enabling a system to tolerate faulty output devices.

We could replicate the output node to avoid the problem mentioned above. This replication can be done when every output node combines the output of all state machine replicas and sends its output to a stream or channel where all output nodes send their outputs.

If output nodes can exhibit Byzantine failures, then the output generated by a majority of $2t+1$ replicated output nodes will provide $t$ fault tolerance. If output nodes can only exhibit fail-stop failures, then any of the replicated $t+1$ nodes will produce the correct output.

Outputting inside the system#

Suppose any component inside the system has to receive the output, such as a client. In that case, it should wait for identical replies from $t+1$ replicas when Byzantine failures are possible and consider the output from any single replica as valid if only fail-stop failures are possible.

Note: The basic tenet to tolerate failures relies on replication and then carefully picking the output.

Fault-tolerant clients#

Implementing a $t$ fault-tolerant system also requires tolerance against faulty clients that make requests causing erroneous output from state machines or resulting in a state machine processing subsequent requests incorrectly. Let's see how we can provide fault tolerance in this scenario.

Replicating the client#

One way to avoid faulty clients is replicating them to have multiple clients that fail independently. For an $N$-fold replication of a client, any state machine that interacted with this client now receives $N$ times the requests; one request by a client previously will be sent by all $N$ replicas.

Requests sent out by client replicas for a single request will not be the same. They will have different unique identifiers, and requests might have different content when the client has not been replicated as a state machine. For example, if a client requests by reading off some time-sensitive sensor, its replicas might make different requests. We will discuss both of these cases.

In the first case, when corresponding requests from client replicas can only differ in their unique identifier, we must improve our state machine model so that state machines receive $N$ requests for a single request. We will not have a state machine $sm$ process each of the $N$ requests it receives from client replicas. Instead, $sm$ will collect requests and execute the corresponding command when a certain number of requests has been collected. Here is how we will determine this threshold number:

1. If clients can exhibit Byzantine failures, then a $t$ fault-tolerant client will require $2t+1$ replicas, and $sm$ will execute the command after it receives its request from $t+1$ client replicas.

2. For fail-stop failures, a $t$ fault-tolerant client will have $t+1$ replicas; the first request received from any replica is sufficient for $sm$ to execute the command.

Handling the case where client replica requests can vary in terms of their content requires using the application's workings. The objective is to ensure that our state machine executes a single command after receiving one or more client replica requests while maintaining fault tolerance.

For example, let’s look at our previous example of a client that reads from a sensor. When receiving client requests with different sensor values, the state machine could process a request with a median of values it received. Now, if Byzantine failures are possible, $t$ fault tolerance requires having $2t+1$ replicas. When receiving $2t+1$ requests with sensor values, taking the median becomes a reasonable approach to ensure that $sm$ uses a non-faulty value from the request.

Defensive programming#

There are circumstances when we cannot replicate clients. This may be because of a lack of hardware, or the application might be designed in a way that its clients cannot be replicated. In this situation, we must modify our state machine to minimize the effect of requests from faulty clients.

For instance, in our memory example, a client can write to all locations of the memory. A faulty client could overwrite in all locations and potentially destroy all information. We can limit write requests from clients so that they can only write to certain locations.

One way to avoid the effects of faulty clients is to include tests in commands. These tests are of the validity of requests, and if requests fail such tests, the pertinent client can be deemed faulty.

Let's consider our mutex example. The mutex state machine will execute a release command from any client, even the one not accessing the resource. Only the client with current access to the resource should be able to release the resource. We could have our mutex ignore release commands from other clients. Here is the updated release command:

It is also possible for a faulty client to acquire the resource and refuse to release it, i.e., not issuing the release command. We will need to limit the duration for which a client can access the resource. With a time limit, we can schedule a release within the acquire command. We will implement the timeout by scheduling a request for the state machine with a greater unique identifier so that the request becomes stable sometime in the future. Such a command does not need to be sent to other replicas since they will schedule it themselves. Let’s update the mutex command so that acquire automatically schedules a release of the resource:

The schedule(command, time) function assigns a unique identifier to the command to become stable after time amount of time has passed. This is done by assigning a unique identifier to command that is time greater than the unique identifier of the command from where schedule is called. Here, schedule assigns the command mutex.timeout(time_granted) a unique identifier B greater than the unique identifier of the current acquire command from where schedule is being called. Also, note that a resource can be released by either the client that has current access to the resource or by timeout.

What's next?#

In the next lesson, we will discuss how to replace faulty replicas with non-faulty replicas.